package demo8;

/**
 * 01背包-目标和
 */
public class test4 {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int aim = (sum + target) / 2;
        // 边界情况
        if(aim < 0 || (sum + target) % 2 == 1) return 0;
        int n = nums.length;
        int[][] dp = new int[n+1][aim+1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= aim; j++) {
                dp[i][j] = dp[i-1][j];
                if(j >= nums[i-1]) {
                    dp[i][j] += dp[i-1][j - nums[i-1]];
                }
            }
        }
        return dp[n][aim];
    }
    // 优化
    public int findTargetSumWays2(int[] nums, int target) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int aim = (sum + target) / 2;
        // 边界情况
        if(aim < 0 || (sum + target) % 2 == 1) return 0;
        int n = nums.length;
        int[] dp = new int[aim+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = aim; j >= nums[i-1]; j--) {
                dp[j] += dp[j - nums[i-1]];
            }
        }
        return dp[aim];
    }
}
